
var initVal={
	// 为了圆形显示完全，默认的圆心偏移量
	defaultCX:25,
	defalutCY:25,
	top:5,
	left:5,
	// 默认半径
	defaultR:25,
	// 每一层行的高度设置
	colStep:50,
	// 同一行的内容，每一个之间的间隔
	rowItemStep:30,
	redStyle:{
		color:"red",
		width:2,
		fill:"red",
		fontFill:"white"
	},
	blackStyle:{
		color:"black",
		width:2,
		fill:"black",
		fontFill:"white"
	},
	font:{
		xOffsetStep: 9,
		yOffset: 6
	},
	initDepth:function(){
		initVal.colMaxDepth = 0;
		initVal.rowMaxDepth = 0;
	},
	// 最深的树深度
	colMaxDepth:0,
	setMaxCol:function(colDepth){
		var t = initVal.colMaxDepth;
		if(colDepth>t){
			initVal.colMaxDepth = colDepth;
		}
	},
	// 返回svg的大小设置 Y的大小
	getMaxCol:function(){
		return initVal.colStep * initVal.colMaxDepth + initVal.defalutCY * 2 + initVal.top * 2;
	},
	// 最大的横向纵深
	rowMaxDepth:0,
	setRowDepth:function(rowDepth){
		var t = initVal.rowMaxDepth;
		if(rowDepth>t){
			initVal.rowMaxDepth = rowDepth;
		}
	},
	// 返回Svg的大小设置，X的大小
	getMaxRow:function(){
		return initVal.rowItemStep * initVal.rowMaxDepth +initVal.defaultCX * 2 + initVal.left * 2;
	},
	img:new ImgStack()
}

// 图形内容堆栈
function ImgStack() {
	this.stack = null;
	// 打开堆栈存储内容的标记
	this.isOpenStack = true;
	this.index = 1;
	this.imgInit=function(){
		this.index = 1;
		this.stack = [];
	}
	this.add = function(tree,txt){
		if(!this.isOpenStack){
			return ;
		}
		
		var item = [];
		item.push(tree);
		var svg = new SVG(item);
		initVal.initDepth();
		tree.afterCompute = function(){
			svg.setSize(initVal.getMaxRow(),initVal.getMaxCol());
		}
		var svghtml = svg.draw();
		
		var html = '<div style="float:left;border:1px solid #ccc">'
						+'<div style="background-color:#333;color:#FFF">'+
							'NO.'+(this.index++) + (tool.isNull(txt)?"":txt)
						+'</div>'
						+ svghtml
					+'</div>';
		this.stack.push(html);
	}
}
// 不运算堆栈
// initVal.imgStack.isOpenStack = false;

/**
 * 树形结构图，要求值相等并且hash值也相等
 */
function Tree(){
	// 顶部节点
	this.head = null;
	this.clone = function(){
		var newTree = new Tree();
		if(!this.isNull(this.head)){
			newTree.head = this.head.clone(null);
		}
		return newTree;
	}
	// 增加一个节点
	this.add = function(key,value){
		// 首先判断key是否为空
		if(tool.isNull(key)){
			return "增加失败，key为空";
		}
		// 初始化显示步骤的图像内容
		initVal.img.imgInit();
		initVal.img.add(this,"增加前["+key+"]");
		if(this.isNull(this.head)){
			this.head = new TreeNode(key,value,null);
			this.head.isRed = false;
			initVal.img.add(this,"增加结束");
			console.log("ADD:HEAD->"+key);
			return "";
		}
		for(var local = this.head;;){
			var comp = this.compare(local.key,key)
			// 注意，此处简化模型，使用key为number,当hash相等时，直接认为两者相等了。
			// 实际处理时，需要对比key是否相等，存在hash相等但是key不相等的情况，还需要仔细进行区分
			if( 0 == comp && local.key === key){
				local.value = value;
				initVal.img.add(this,"数值修改["+key+"]");
				return "";
			}
			// comp大于0 local.key大于key key在local的左子树上
			else if(0 < comp){
				if(local.left == null || local.left == undefined){
					local.left = new TreeNode(key,value,local);
					initVal.img.add(this,"增加成功，平衡前");
					console.log("ADD:"+local.key+"-Left->"+key);
					this.addBalance(local.left);
					initVal.img.add(this,"增加成功，平衡结束");
					break;
				}
				else 
					local = local.left;
			}
			// comp小于0 local.key小于key key在local的右子树上
			else if(0 > comp){
				if(local.right == null || local.right == undefined){
					local.right = new TreeNode(key,value,local);
					initVal.img.add(this,"增加成功，平衡前");
					console.log("ADD:"+local.key+"-Right->"+key);
					this.addBalance(local.right);
					initVal.img.add(this,"增加成功，平衡结束");
					break;
				}
				else 
					local = local.right;
			}
			else{
				throw new Error("出现hash相等，但是key值不相等的内容尚未处理");
			}
		}
	}
	// 左旋 按照当前节点进行左旋
	this.rotateLeft = function(local){
		var p = local,pp = p.parent,pr = p.right,prl = pr.left;
		// 当前节点成为右子树的左节点
		pr.left = p;
		// 当前节点的父节点为右子树
		p.parent = pr;
		if(!this.isNull(prl)){
			// 右子树的左节点为当前的右节点
			p.right = prl;
			prl.parent = p;
		}
		else{
			p.right = null;
		}
		if(!this.isNull(pp)){
			pr.parent = pp;
			// 当前节点的父父节点重新指向右节点
			if(p == pp.left){
				pp.left = pr;
			}
			else{
				pp.right = pr;
			}
		}
		else{
			pr.parent = null;
			this.head = pr;
		}
	}
	// 右旋
	this.rotateRight = function(local){
		var p = local,pp = p.parent,pl=p.left,plr = pl.right;
		// 当前节点成为左节点的右节点
		pl.right = p;
		p.parent = pl;
		if(!this.isNull(plr)){
			// 左子树的右节点成为当前的左节点
			p.left = plr;
			plr.parent = p;
		}
		else{
			p.left = null;
		}
		if(!this.isNull(pp)){
			pl.parent = pp;
			// 当前节点父父节点指向新的左节点
			if(p == pp.left){
				pp.left = pl;
			}
			else{
				pp.right = pl;
			}
		}
		else{
			pl.parent = null;
			this.head = pl;
		}
		
	}
	// 一步一停的话,需要写一个队列,点击一个操作之后
	// 所有的操作变更成队列的内容,然后点击一步执行一个操作
	/**
	 * 增加后平衡
	 * @param {Object} local 当前新增的节点
	 */
	this.addBalance = function(local){
		for(var x = local,xp,xpp,xppr;;){
			/**
			 * 1、新增的节点父节点为空，当前节点为根节点
			 * 2、当前节点的父亲节点为黑色，当前节点改为红色完成
			 * 3、父节点红，父父肯定不为空，
			 * 3.1 父为父父的左节点
			 * 		3.1.1 父父节点有右子树 并且右子树也为红
			 * 			父节点和父父右修改为黑色，父父为红色，父父节点，向上继续传递处理
			 * 		3.1.2 父父节点无右子树
			 * 3.2 父为父父的右节点
			 * 		3.2.1父父节点有左子树 并且也为红
			 * 			父节点和父父左修改为黑色，父父为红色，父父节点向上传递
			 *		3.2.2父父节点无左子树
			 */
			// 1 新增的节点父节点为空，当前节点为根节点
			if(this.isNull(xp=x.parent)){
				this.head = x;
				x.isRed = false;
				initVal.img.add(this,"修改根节点为红色");
				return ;
			}
			// 2、当前节点的父亲节点为黑色，当前节点改为红色完成
			if(!xp.isRed){
				x.isRed = true;
				initVal.img.add(this,"修改当前节点["+x.key+"]为红色");
				return ;
			}
			// 3、父节点红，父父肯定不为空
			if(this.isNull(xpp = xp.parent)){
				alert("当前二叉树出现问题，"+xp.key+"节点的上级为空");
				throw new Error("原二叉树就不平衡,出现待排查的问题");
			}
			// 3.1 父为父父的左节点
			if(xp == xpp.left){
				// 		3.1.1 父父节点有右子树 && xppr.isRed
				if(!this.isNull(xppr = xpp.right) && xppr.isRed){
					// 父节点和父父右修改为黑色，父父为红色，父父节点，向上继续传递处理
					initVal.img.add(this,"父["+xp.key+"]为父父左，父父右为红，调整前");
					xp.isRed = false;
					xpp.right.isRed = false;
					xpp.isRed = true;
					initVal.img.add(this,"父["+xp.key+"]为父父左，父父右为红，调整后");
					x = xpp;
				}
				// 3.1.2 父父节点无右子树
				else{
					// 当前节点为父右
					if(x == xp.right){
						initVal.img.add(this,"父["+xp.key+"]为父父左，父父右为为空或黑，当前为父右，父左旋,调整父亲与当前节点顺序");
						// 按照父节点进行左旋
						this.rotateLeft(xp);
						// 父节点和当前节点位置互换
						var t = xp;
						xp = x;
						x = t;
					}
					// 当前节点为父左
					// 以父父节点进行右旋
					initVal.img.add(this,"父["+xp.key+"]为父父左，父父右为为空或黑，当前为父左，父父右旋调整");
					this.rotateRight(xpp);
					// 父节点为黑色，父父和当前节点为红色
					initVal.img.add(this,"右旋完成");
					xp.isRed = false;
					x.isRed = true;
					xpp.isRed = true;
					initVal.img.add(this,"颜色调整完成");
					// 已经平衡,完毕
					return ;
				}
			}
			// * 3.2 父为父父的右节点
			else{
				// 3.2.1父父节点有左子树 && xpp.left.isRed
				if(!this.isNull(xpp.left) && xpp.left.isRed ){
					// 父节点和父父左修改为黑色，父父为红色，父父节点，向上继续传递处理
					initVal.img.add(this,"父["+xp.key+"]为父父右，父父左为红，调整前");
					xp.isRed = false;
					xpp.left.isRed = false;
					xpp.isRed = true;
					initVal.img.add(this,"调整后");
					x = xpp;
				}
			// *		3.2.2父父节点无左子树
				else{
					// 当前节点为父左
					if(x == xp.left){
						initVal.img.add(this,"["+xp.key+"]父为父父右，父父左为为空或黑，当前为父左，父右旋调整，更换父亲和当前节点位置");
						// 按照父节点进行右旋
						this.rotateRight(xp);
						// 父节点和当前节点位置互换
						var t = xp;
						xp = x;
						x = t;
					}
					// 当前节点为父右
					// 以父父节点进行左旋
					initVal.img.add(this,"父["+xp.key+"]为父父右，父父左为为空或黑，当前为父右，父父左旋调整");
					this.rotateLeft(xpp);
					// 父节点为黑色，父父和当前节点为红色
					initVal.img.add(this,"左旋完成");
					xp.isRed = false;
					x.isRed = true;
					xpp.isRed = true;
					initVal.img.add(this,"颜色调整");
					// 已经平衡,完毕
					return ;
				}
			}
		}
	}
	// 比较key1和key2的值大小
	this.compare = function(key1,key2){
		if(key1 > key2){
			return 1;
		}
		else if(key1 < key2){
			return -1;
		}
		else
			return 0;
	}
	// 根据key获取一个数据
	this.get = function(key){
		// 首先判断key是否为空
		if(tool.isNull(key)){
			return "key为空";
		}
		// 首先获根节点，判断根节点是否为空
		if(tool.isNull(this.head)) return "树为空";
		// 循环准备，首先判断自己，其次是左右子
		// 简洁命名，x指当前节点，l左子，r右子，p父节点
		for(var x=this.head,xl,xr;;){
			// 根据key值的大小去判断，应该进入左子还是右子
			var comp = this.compare(key , x.key)
			// 注意，此处简化模型，使用key为number,当hash相等时，直接认为两者相等了。
			// 实际处理时，需要对比key是否相等，存在hash相等但是key不相等的情况，还需要仔细进行区分
			// 对比是不是自己
			if(comp ==0 && x.key == key){
				return x;
			}
			// 新节点大 找右子
			else if(comp > 0){
				if(!tool.isNull(x.right)){
					x = x.right;
				}
				else{
					return "尚未找到";
				}
			}
			// 新节点小 找左子
			else if(comp < 0){
				if(!tool.isNull(x.left)){
					x = x.left;
				}
				else{
					return "尚未找到";
				}
			}
			else{
				throw new Error("出现hash相等，但是key值不相等的内容尚未处理");
			}
			
		}
	}
	/**
	 * 按照key删除内容
	 * @param {Object} key
	 */
	this.remove = function(key){
		// 首先判断key是否为空
		if(tool.isNull(key)){
			return "删除失败：key为空";
		}
		// 其次判断key存在不存在
		var x = this.get(key);
		if(tool.isNull(x) || typeof x == "string"){
			return "尚未找到Key:"+key+"的节点";
		}
		/**
		 * 判断待删除的节点有没有左右子树
		 * 1、一个都没有
		 * 		当前节点是否为红
		 * 			是，直接删除
		 * 			否，为黑，标记后平衡处理 4 
		 * 2、有一个
		 * 		当前节点是否为红
		 * 			是，不可能存在只有一个子节点并且自己还为红的情况
		 * 			否，为黑，只有一个节点，再往下不可能有节点了，删除并填充，并改为黑。
		 * 3、有两个，找继承者
		 * 		寻找右子节点的的最底层的左子
		 * 		然后相互替换，包含节点，颜色等内容。
		 * 		当前节点有无右节点
		 * 			有，删除当前节点黑，右节点红填充，右改为黑
		 * 			无，当前节点
		 * 				为红则直接删除
		 * 				为黑，进入4
		 * 4、当前节点为黑，为父左
		 * 		父右为黑
		 * 			父左右为空，或者为红
		 * 		父右为红
		 * 			父右右，右左均为黑
		 * 	 当前节点为父右，一致
		 */
		
		// 初始化显示步骤的图像内容
		initVal.img.imgInit();
		
		// xl 左子 xr右子 xp 父 xpr 父右 xpl 父左
		var xl = x.left,xr = x.right,xp = x.parent,readToDel;
		// var xpr = xp.right,xpl = xp.left;
		// 情况三左右都不为空
		if(!tool.isNull(xl)&&!tool.isNull(xr)){
			initVal.img.add(this,"当前节点["+x.key+"]，有两个子节点，寻找继承者并替换");
			var s = xr;
			// 获取右子最左的节点
			while(!tool.isNull(s.left))s=s.left;
			// 首先替换颜色
			var color;
			color = s.isRed;
			s.isRed = x.isRed;
			x.isRed = color;
			// 替换当前节点和s节点的位置
			if(s == xr){
				var sr;
				// 父节点
				xr.parent = xp;
				// xr无左节点
				xr.left = x.left;
				if(!tool.isNull(xr.left))xr.left.parent = xr;
				sr = xr.right;
				xr.right = x;
				if(!tool.isNull(xp)){
					var xpr = xp.right,xpl = xp.left;
					if(x == xpl)xp.left = xr;
					else xp.right = xr;
				}
				else{
					this.head = xr;
				}
				x.parent = xr;
				x.left = null;
				x.right = sr;
				if(!tool.isNull(sr))sr.parent = x;
				
			}
			else{
				var sr,sp;
				sp = s.parent;
				sr = s.right;
				// 父节点
				s.parent = xp;
				// xr无左节点
				s.left = x.left;
				s.right = x.right;
				if(!tool.isNull(s.right))s.right.parent = s;
				if(!tool.isNull(s.left))s.left.parent = s;
				if(!tool.isNull(xp)){
					var xpr = xp.right,xpl = xp.left;
					if(x == xpl)xp.left = s;
					else xp.right = s;
				}
				else{
					this.head = s;
				}
				x.parent = sp;
				sp.left = x;
				x.left = null;
				x.right = sr;
				if(!tool.isNull(sr))sr.parent = x;
			}
			// 标记为待删除的对象
			if(!tool.isNull(x.right))readToDel = x.right;
			else readToDel = x;
			initVal.img.add(this,"寻找到继承者，替换完成");
		}
		// 左不为空
		else if(!tool.isNull(xl)){
			readToDel = xl;
		}
		// 右不为空
		else if(!tool.isNull(xr)){
			readToDel = xr;
		}
		// 全为空
		else{
			readToDel = x;
		}
		// 当前x就是要删除的那个
		if(readToDel != x){
			initVal.img.add(this,"节点["+x.key+"]存在右节点，删除并顶替");
			// 删除x并添加至上级
			if(tool.isNull(x.parent)){
				this.head = readToDel;
			}
			else{
				readToDel.parent = xp = x.parent;
				if(x == xp.left)xp.left = readToDel;
				else xp.right = readToDel;
			}
			// 清空并删除
			x.parent = null;
			x.left = null;
			x.right = null;
			initVal.img.add(this,"替换完成");
		}
		// 如果待删除的节点为红色，直接删除，否则进行平衡
		if(!x.isRed) this.deleteBalance(readToDel);
		// 然后删除
		if(readToDel == x){
			initVal.img.add(this,"删除节点["+x.key+"]");
			if(tool.isNull(xp = x.parent)){
				this.head = null;
			}
			else {
				if(x == xp.left)xp.left = null;
				else xp.right = null;
			}
			// 清空并删除
			x.parent = null;
			x.left = null;
			x.right = null;
			initVal.img.add(this,"删除完成");
		}
		x = null;
		// 
		return "删除完成";
	}
	this.deleteBalance = function(x){
		for(;;){
			var xp,xpl,xpr;
			// 缺少处理当前节点为空的情况
			if(tool.isNull(x) || x == this.head){
				initVal.img.add(this,"待平衡节点为根节点");
				return;
			}
			// 对整理的内容进行整理
			// 当前节点为根节点
			if(tool.isNull(xp = x.parent)){
				initVal.img.add(this,"待平衡节点为根节点["+x.key+"]");
				x.isRed = false;
				initVal.img.add(this,"调整完成");
				return ;
			}
			// 只有左子，只有右子，(两个都有，会转换为只有右子，或者什么都没有)，什么都没有
			// 只有左子，只有右子，删除并填充，当前节点为红，改为黑色即可。
			if(x.isRed){
				initVal.img.add(this,"待平衡节点为根节点["+x.key+"]+为红色，为已经删除并顶替的部分");
				x.isRed = false;
				initVal.img.add(this,"调整完成");
				return ;
			}
			// 剩余情况为，当前节点为黑，没有子节点
			// 情况1，当前节点为父节点的左子树
			if((xpl = xp.left) == x){
				// 1、父亲节点的右节点为红，父右的双子为黑。以父右
				if(!tool.isNull(xpr = xp.right)&& xpr.isRed){
					initVal.img.add(this,"当前为父左["+x.key+"]，父父右为红色");
					// 父节点置为红，父右置为黑，以父，右旋
					xp.isRed = true;
					xpr.isRed = false;
					this.rotateRight(xp);
					// 以当前节点更新父，父右节点
					xpr = tool.isNull(xp = x.parent)?null:xp.right; 
					initVal.img.add(this,"变更完成");
				}
				// 2、父节点的右节点为黑,或者为空
				if(tool.isNull(xpr)){
					x = xp;// 更新并继续操作
				}
				else{
					var sl = xpr.left,sr = xpr.right;
					// 父右节点为黑，四种情况，全为空，左或者右有，或者两个都有
					// 全为空，或者都为黑，已经没有调整的余地了
					if((tool.isNull(sl)||!sl.isRed)
					&&(tool.isNull(sr)||!sr.isRed)){
						initVal.img.add(this,"当前为父左["+x.key+"]，父右为黑，父右左右为黑或为空");
						// 当前节点置为红，更新并继续循环吧。
						xpr.isRed = true;
						x = xp;
						initVal.img.add(this,"颜色变更完毕");
					}
					else{
						// 因为父右左，需要转换父右右来操作，首先判断这个
						if(tool.isNull(sr)||!sr.isRed){
							initVal.img.add(this,"当前为父左["+x.key+"]，父右为黑，父右左需要转换为父右右");
							// 左置为黑，父右置为红，右旋
							if(!tool.isNull(sl))sl.isRed = false;
							xpr.isRed = true;
							// 以xpr右旋
							this.rotateRight(xpr);
							// 更新内容
							xpr = tool.isNull(xp = x.parent)?null:xp.right; 
							initVal.img.add(this,"变换完毕");
						}
						initVal.img.add(this,"当前为父左["+x.key+"]，父右为黑，父右右变更，父右为父颜色，父和父右右为黑色，父左旋");
						// 父右右，左右都有的。
						// 父右右置为黑，父右为原来父亲的颜色，父为黑，以父左旋,这样就平衡了
						if(!tool.isNull(xpr)){
							xpr.isRed = tool.isNull(xp)?false:xp.isRed;
							if(!tool.isNull(sr = xpr.right))sr.isRed = false;
						}
						// 以xp 左旋，与原来一样的平衡
						if(!tool.isNull(xp)){
							xp.isRed = false;
							this.rotateLeft(xp);
						}
						x = this.head;
						initVal.img.add(this,"变换完毕");
					}
				}
			}
			// 情况2，当前节点为父节点的右子树
			else{
				// 1、父亲节点的左节点为红，父左的双子为黑。以父右
				if(!tool.isNull(xpl = xp.left)&& xpl.isRed){
					initVal.img.add(this,"当前为父右["+x.key+"]，父左为红，右旋");
					// 父节点置为红，父右置为黑，以父，右旋
					xp.isRed = true;
					xpl.isRed = false;
					this.rotateRight(xp);
					// 以当前节点更新父，父右节点
					xpl = tool.isNull(xp = x.parent)?null:xp.left; 
					initVal.img.add(this,"完成");
				}
				// 2、父节点的右节点为黑,或者为空
				if(tool.isNull(xpl)){
					x = xp;// 更新并继续操作
				}
				else{
					var sl = xpl.left,sr = xpl.right;
					// 父左节点为黑，四种情况，全为空，左或者右有，或者两个都有
					// 全为空，或者都为黑，已经没有调整的余地了
					if((tool.isNull(sl)||!sl.isRed)
					&&(tool.isNull(sr)||!sr.isRed)){
						initVal.img.add(this,"当前为父右["+x.key+"]，父左为黑，父左的左右子为黑或者空");
						// 当前节点置为红，更新并继续循环吧。
						xpl.isRed = true;
						x = xp;
						initVal.img.add(this,"调整完成");
					}
					else{
						// 因为父左右，需要转换父左左来操作，首先判断这个
						if(tool.isNull(sl)||!sl.isRed){
							initVal.img.add(this,"当前为父右["+x.key+"]，父左为黑，父左右需调整为父左左");
							// 右置为黑，父左置为红，左旋
							if(!tool.isNull(sr))sr.isRed = false;
							xpl.isRed = true;
							// 以xpl左旋
							this.rotateLeft(xpl);
							// 更新内容
							xpl = tool.isNull(xp = x.parent)?null:xp.left; 
							initVal.img.add(this,"调整完成");
						}
						initVal.img.add(this,"当前为父右["+x.key+"]，父左为黑，父左左，父左为父颜色，父和父左左为黑色，父右旋");
						// 父左右，左左都有的。
						// 父左左置为黑，父左为原来父亲的颜色，父为黑，以父右旋,这样就平衡了
						if(!tool.isNull(xpl)){
							xpl.isRed = tool.isNull(xp)?false:xp.isRed;
							if(!tool.isNull(sl = xpl.left))sl.isRed = false;
						}
						// 以xp 右旋旋，与原来一样的平衡
						if(!tool.isNull(xp)){
							xp.isRed = false;
							this.rotateRight(xp);
						}
						initVal.img.add(this,"完成");
						x = this.head;
					}
				}
			}
		}
	}
	// 删除所有内容
	this.removeAll = function(){
		// 不用书写了、最简单的。
	}
	/**
	 * 执行计算内容之后
	 * 请勿删除，执行结果之后的回调内容
	 */
	this.afterCompute = function (){}
	this.draw = function(){
		if(this.head != undefined && this.head != null){
			this.head.compute();
			this.afterCompute();
			return this.head.draw();
		}
		else 
			return "";
	}
	this.isNull= function(obj){
		if(obj == null || obj == undefined){
			return true;
		}
		else return false;
	}
}
/**
 * @param {Object} key 键
 * @param {Object} value 值
 * @param {TreeNode} parent 父节点
 * @param {TreeNode} left 左子节点
 * @param {TreeNode} right 右子节点
 */
function TreeNode(key,value,parent){
	this.key = key;
	this.value = value;
	this.parent = parent;
	this.left = null;
	this.right = null;
	// 颜色
	this.isRed = true;
	// 设置当前节点的树深度
	this.colDepth = -1;
	// 当前节点的横向纵深
	this.rowDepth = -1;
	this.isNull= function(obj){
		if(obj == null || obj == undefined){
			return true;
		}
		else return false;
	}
	this.clone = function(parent){
		var newNode = new TreeNode(this.key,this.value,parent);
		if(!this.isNull(this.left)){
			newNode.left = this.left.clone(newNode);
		}
		if(!this.isNull(this.right)){
			newNode.right = this.right.clone(newNode);
		}
		newNode.isRed = this.isRed;
		newNode.colDepth = this.colDepth;
		newNode.rowDepth = this.rowDepth;
		return newNode;
	}
	// 定义的圆心位置
	this.cx = null;
	this.cy = null;
	
	// 定义的原型内容的位置
	this.circle = null;
	// 自己和父亲节点的连线
	this.line = null;
	// 文字的位置
	this.text = null;
	
	/**
	 * 计算思路根在上，节点在下，节点在Y轴的投影为col 在X轴的投影为row从左到右
	 * @param {Object} colD 竖向深度
	 * @param {Object} rowD 横向深度
	 */
	this.compute = function(rowD){
		// 首先计算col值，深入一层则加1
		if(this.isNull(this.parent)){
			// 证明当前节点是顶级节点
			this.colDepth = 0;
		}
		else{
			this.colDepth = this.parent.colDepth + 1;
		}
		
		// 开始计算row的值
		// 左侧为空
		if(this.isNull(this.left)){
			// 左和上为空则为根节点并且左为空
			if(this.isNull(this.parent)){
				this.rowDepth = rowD = 0;
			}
			else{
				if(this.isNull(rowD)){
					this.rowDepth = rowD = 0;
				}
				else{
					this.rowDepth = rowD += 1;
				}
			}
		}
		else{
			// 计算数据完成之后
			rowD = this.left.compute(rowD);
			this.rowDepth = rowD += 1;
		}
		if(!this.isNull(this.right)){
			rowD = this.right.compute(rowD);
		}
		initVal.setMaxCol(this.colDepth);
		initVal.setRowDepth(this.rowDepth);
		// 当前节点计算完毕
		this.cy = initVal.colStep * this.colDepth + initVal.defalutCY + initVal.top;
		this.cx = initVal.rowItemStep * this.rowDepth +initVal.defaultCX + initVal.left;
		return rowD;
	}
	this.draw = function(){
		var html = "";
		if(!this.isNull(this.right))html += this.right.lineDraw();
		if(!this.isNull(this.left)){
			html += this.left.lineDraw();
			html += this.left.draw();
		}
		html+=this.localDraw();
		if(!this.isNull(this.right)){
			html += this.right.draw();
		}
		
		return html;
	}
	// 有些父亲节点的数据尚未初始化
	this.lineDraw = function(){
		var x1,y1,x2,y2,stroke,strokeWidth,fill;
		stroke = initVal.blackStyle.color;
		strokeWidth = initVal.blackStyle.width;
		fill = initVal.blackStyle.fill;
		var html = "";
		// 计算两个点和圆心的相交线，连接相交线
		
		x1=this.cx;
		y1=this.cy;
		x2=this.parent.cx;
		y2=this.parent.cy;
		
		// 对线条赋值或者新增
		if(!this.isNull(this.parent)){
			if(this.isNull(this.line)){
				this.line = new line(x1,y1,x2,y2,stroke,strokeWidth)
			}
			else{
				this.line.setValues(x1,y1,x2,y2,stroke,strokeWidth);
			}
			html += this.line.draw();
		}
		return html;
	}
	// 必须有的字段，输出显示内容
	this.localDraw = function(){
		var cx,cy,r,stroke,strokeWidth,fill,fontFill;
		// 计算当前节点的圆心
		cy = this.cy;
		cx = this.cx;
		// 获取当前节点的半径
		r = initVal.defaultR;
		// 针对当前的颜色进行自定义的修改判断
		if(this.isRed){
			stroke = initVal.redStyle.color;
			strokeWidth = initVal.redStyle.width;
			fill = initVal.redStyle.fill;
			fontFill = initVal.redStyle.fontFill;
		}
		else{
			stroke = initVal.blackStyle.color;
			strokeWidth = initVal.blackStyle.width;
			fill = initVal.blackStyle.fill;
			fontFill = initVal.blackStyle.fontFill;
		}
		// 返回的内容值
		var html = "";
		// 赋值或新增
		if(this.isNull(this.circle)){
			this.circle = new circle(cx,cy,r,stroke,strokeWidth,fill);
		}
		else{
			this.circle.setValues(cx,cy,r,stroke,strokeWidth,fill);
		}
		html += this.circle.draw();
		// 开始增加文字内容显示，显示Key
		var xOffset = 0 - ((this.key+"").length/2*initVal.font.xOffsetStep)
		var textCx = this.cx + xOffset;
		var textCy = this.cy + initVal.font.yOffset;
		if(this.isNull(this.text)){
			this.text = new text(textCx,textCy,fontFill,this.key);
		}
		else{
			this.text.setValues(textCx,textCy,fontFill,this.key);
		}
		html+= this.text.draw();
		return html;
	}
}

